package org.example.myleet.p1011;

/**
 * 13 ms
 * 二分法，找到答案可能存在的左右边界以及判断答案在左右两部分的标准，用二分法快速寻找答案
 */
public class Solution {
    public int shipWithinDays(int[] weights, int D) {
        //答案的左边界是最重货物的重量，右边界是所有货物的总重量，即载重的船最小也要是最重货物的重量（最多w天运完），最大是所有货物的总重量（一天运完）
        int maxWeight = Integer.MIN_VALUE, sumWeight = 0;
        for (int weight : weights) {
            maxWeight = Math.max(maxWeight, weight);
            sumWeight += weight;
        }
        int l = maxWeight, r = sumWeight;
        while (r - l > 1) {
            int midCapacity = (r + l) / 2;
            if (canTransport(weights, D, midCapacity)) {
                //如果此运力可以在D天内运完，船再小一点也可以，那么答案在左半部分
                r = midCapacity;
            } else {
                //如果此运力不可以在D天内运完，则船必须更大一点，那么答案在右半部分
                l = midCapacity;
            }
        }
        //最后判断准确的结论
        return canTransport(weights, D, l) ? l : r;
    }

    /**
     * 在capacity运力情况下是否可以在D天内运完
     */
    private boolean canTransport(int[] weights, int D, int capacity) {
        int day = 0, load = 0;
        for (int weight : weights) {
            if (load <= capacity - weight) {
                //未超重，安排在同一天运
                load += weight;
            } else {
                //超重，安排在第二天运
                load = weight;
                ++day;
            }
        }
        //最后还有一批需要运送，安排多一天
        ++day;
        return day <= D;
    }
}
